/**
 * @author 徐楠
 * @date 2022/4/2 15:33
 * @version 1.0
 */

package com.xunan.likou;

public class DiagonalTraversal {
    public static void main(String[] args) {
        //1 2 6 11 7 3 4 8 12 13 9 5 10 14 15
        //int[][] mat = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}};
        //1 2 4 7 5 3 6 8 9
        //int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        //1 2 3 4
        //int[][] mat = {{1, 2}, {3, 4}};
        //1 2 4 7 5 3 6 8 10 13 11 9 12 14 15
        //int[][] mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}, {13, 14, 15}};
        //1 2
        //int[][] mat = {{1,2}};
        //1 2
        //int[][] mat = {{1}, {2}};
        //1
        //int[][] mat = {{1}};
        //int[][] mat = {{6, 9, 7}};
        int[][] mat = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}};
        System.out.println();
        int[] diagonalOrder = findDiagonalOrder(mat);
        for (int i : diagonalOrder) {
            System.out.print(i + " ");
        }

        /*System.out.println();
        for (int i = 0; i < 10; i++) {
            System.out.println("i " + (i & 1));
        }*/
    }

    /**
     * 无法承载较大的mat
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        //列长
        int x = mat.length;
        //行长
        int y = mat[0].length;
        System.out.println(x);
        System.out.println(y);
        //找对角线最大长度
        int diagonalLength = x;
        if (x > y) {
            diagonalLength = y;
        }

        int index = 0;
        int[] result = new int[x * y];

        int count = x + y - 1;
        int temp = 1;
        int down = 1;
        int t = 2;

        if (x == 1 || y == 1) {
            for (int[] ints : mat) {
                for (int anInt : ints) {
                    result[index++] = anInt;
                }
            }
            return result;
        }

        if (x == 2 || y == 2) {
            t = 2;
            result[index++] = mat[0][0];

            if (x <= y) {
                System.out.println("y 长");
                System.out.println(diagonalLength);
                while (temp < count - 1) {

                    //偶数向上
                    if (temp % 2 == 0) {

                        if (temp >= diagonalLength) {
                            int i = temp - down;
                            int j = down;
                            int frequency = 1;
                            int number = t;
                            while (frequency <= number) {
                                result[index++] = mat[i][j];

                                i--;
                                j++;
                                frequency++;
                            }
                            down++;
                        } else {
                            int i = temp;
                            int j = 0;
                            while (j <= temp) {
                                result[index++] = mat[i][j];
                                i--;
                                j++;
                            }
                        }

                    } else {

                        //奇数向下

                        if (temp >= diagonalLength) {
                            int i = temp - down;
                            int j = down;
                            int frequency = 1;
                            int number = t;
                            int m = index;
                            m = m + number - 1;
                            while (frequency <= number) {
                                result[m--] = mat[i][j];
                                index++;
                                i--;
                                j++;
                                frequency++;
                            }
                            down++;
                        } else {
                            int i = 0;
                            int j = temp;
                            while (i <= temp) {
                                result[index++] = mat[i][j];
                                i++;
                                j--;
                            }
                        }


                    }
                    temp++;


                    System.out.println("*******");
                    for (int i : result) {
                        System.out.print(i + " ");
                    }
                    System.out.println();
                    System.out.println("*******");
                }

            } else {
                System.out.println("x 长");
                System.out.println("diagonalLength " + diagonalLength);


                while (temp < count - 1) {

                    //偶数向上
                    if (temp % 2 == 0) {

                        if (temp >= diagonalLength) {
                            int i = down;
                            int j = temp - down;
                            int frequency = 1;
                            int number = t;
                            int m = index;
                            m = m + number - 1;
                            while (frequency <= number) {
                                result[m--] = mat[i][j];
                                index++;
                                i++;
                                j--;
                                frequency++;
                            }
                            down++;

                        } else {
                            int i = temp;
                            int j = 0;
                            while (j <= temp) {
                                result[index++] = mat[i][j];
                                i--;
                                j++;
                            }
                        }

                    } else {

                        //奇数向下

                        if (temp >= diagonalLength) {

                            int i = down;
                            int j = temp - down;
                            int frequency = 1;
                            int number = t;
                            while (frequency <= number) {
                                result[index++] = mat[i][j];

                                i++;
                                j--;
                                frequency++;
                            }
                            down++;


                        } else {
                            int i = 0;
                            int j = temp;
                            while (i <= temp) {
                                result[index++] = mat[i][j];
                                i++;
                                j--;
                            }
                        }


                    }
                    temp++;



                    System.out.println("*******");
                    for (int i : result) {
                        System.out.print(i + " ");
                    }
                    System.out.println();
                    System.out.println("*******");
                }
            }

            result[index++] = mat[x - 1][y - 1];
            return result;
        }

        result[index++] = mat[0][0];

        if (x <= y) {
            System.out.println("y 长");
            System.out.println(diagonalLength);
            while (temp < count - 1) {

                //偶数向上
                if (temp % 2 == 0) {

                    if (temp >= diagonalLength) {
                        int i = temp - down;
                        int j = down;
                        int frequency = 1;
                        int number = t;
                        while (frequency <= number) {
                            result[index++] = mat[i][j];

                            i--;
                            j++;
                            frequency++;
                        }
                        down++;
                    } else {
                        int i = temp;
                        int j = 0;
                        while (j <= temp) {
                            result[index++] = mat[i][j];
                            i--;
                            j++;
                        }
                    }

                } else {

                    //奇数向下

                    if (temp >= diagonalLength) {
                        int i = temp - down;
                        int j = down;
                        int frequency = 1;
                        int number = t;
                        int m = index;
                        m = m + number - 1;
                        while (frequency <= number) {
                            result[m--] = mat[i][j];
                            index++;
                            i--;
                            j++;
                            frequency++;
                        }
                        down++;
                    } else {
                        int i = 0;
                        int j = temp;
                        while (i <= temp) {
                            result[index++] = mat[i][j];
                            i++;
                            j--;
                        }
                    }


                }
                temp++;

                if (count % 2 == 0) {
                    if (temp < count / 2) {
                        t++;
                    } else if (temp == count / 2) {
                        continue;
                    } else {
                        //temp > count/2
                        t--;
                    }
                } else {
                    if (temp <= (count / 2) - 1) {
                        t++;
                    } else if (temp == count / 2 || temp == (count / 2) + 1) {
                        continue;
                    } else {
                        //t > count/2
                        t--;
                    }
                }

                System.out.println("*******");
                for (int i : result) {
                    System.out.print(i + " ");
                }
                System.out.println();
                System.out.println("*******");
            }

        } else {
            System.out.println("x 长");
            System.out.println("diagonalLength " + diagonalLength);

            while (temp < count - 1) {

                //偶数向上
                if (temp % 2 == 0) {

                    if (temp >= diagonalLength) {
                        int i = down;
                        int j = temp - down;
                        int frequency = 1;
                        int number = t;
                        int m = index;
                        m = m + number - 1;
                        while (frequency <= number) {
                            result[m--] = mat[i][j];
                            index++;
                            i++;
                            j--;
                            frequency++;
                        }
                        down++;

                    } else {
                        int i = temp;
                        int j = 0;
                        while (j <= temp) {
                            result[index++] = mat[i][j];
                            i--;
                            j++;
                        }
                    }

                } else {

                    //奇数向下

                    if (temp >= diagonalLength) {

                        int i = down;
                        int j = temp - down;
                        int frequency = 1;
                        int number = t;
                        while (frequency <= number) {
                            result[index++] = mat[i][j];

                            i++;
                            j--;
                            frequency++;
                        }
                        down++;


                    } else {
                        int i = 0;
                        int j = temp;
                        while (i <= temp) {
                            result[index++] = mat[i][j];
                            i++;
                            j--;
                        }
                    }


                }
                temp++;

                if (count % 2 == 0) {
                    if (temp < count / 2) {
                        t++;
                    } else if (temp == count / 2) {
                        continue;
                    } else {
                        //temp > count/2
                        t--;
                    }
                } else {
                    if (temp <= (count / 2) - 1) {
                        t++;
                    } else if (temp == count / 2 || temp == (count / 2) + 1) {
                        continue;
                    } else {
                        //t > count/2
                        t--;
                    }
                }

                System.out.println("*******");
                for (int i : result) {
                    System.out.print(i + " ");
                }
                System.out.println();
                System.out.println("*******");
            }
        }
        if (x > 1 && y > 1) {
            result[index++] = mat[x - 1][y - 1];
        }


        return result;
    }

    /**
     * 首先确定遍历几遍，可以将矩阵倾斜45度看，每一行就是外层的遍历一次，一共遍历了x + y - 1次
     * 对于每次循环，可以通过奇偶来判断向右上方还是左下方向遍历
     * 如果向右上方向遍历，则遍历指针i j一定向着右上角移动，则i--, j++，但是会到达边界出现越界
     * <p>
     * -------
     * -
     * -
     * -
     * <p>
     * 对于向右上方的越界，有三种情况：
     * 在矩阵上边界越界，此时i < 0 && j < x，要恢复则应该让i++，j不动
     * 在矩阵右上角越界，此时i < 0 && j == x（注意是跳完了之后j = x），要恢复则要让i += 2，j--
     * 在矩阵右边界越界，此时i >= 0 && j > y，要恢复则要让i += 2，j--
     * 我们可以看一下，下边的两个条件是可以合并在一起的，
     * 即j >= x的时候可以把二者合并在一起算，这就是为啥那里要用j < x和j >= x区分
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrderTrue(int[][] mat) {
        int x = mat.length;
        int y = mat[0].length;
        int[] result = new int[x * y];
        int i = 0, j = 0, index = 0;
        for (int count = 0; count < x + y - 1; ++count) {
            //偶
            if ((count & 1) == 0) {
                while (i >= 0 && j < y) {
                    result[index++] = mat[i][j];
                    j++;
                    i--;
                }
                if (j < y) {
                    i++;
                } else {
                    i += 2;
                    j--;
                }
            } else {
                while (i < x && j >= 0) {
                    result[index++] = mat[i][j];
                    i++;
                    j--;
                }
                if (i < x) {
                    j++;
                } else {
                    j += 2;
                    i--;
                }
            }
        }
        return result;
    }

}
